#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "shell.h"

//直接插入排序
void straightInsertSort(int *arr,int len){
	int i,j;
	for(i=1;i<len;i++){
		int temp=arr[i];
		for(j=i-1;j>=0&&arr[j]>temp;j--){
			arr[j+1]=arr[j];
		}
		arr[j+1]=temp;
	}
}

//冒泡排序
void bubbleSort(int *arr,int len){
	for(int i=0;i<len;i++){
		int swaped=0;
		for(int j=1;j<len-i;j++){
			if(arr[j-1]>arr[j]){
				int temp=arr[j-1];
				arr[j-1]=arr[j];
				arr[j]=temp;
				swaped=1;
			}
		}
		if(!swaped){
			return;//已经有序
		}
	}
}
//待步进的插入排序
static void sort(int *arr,int len,int startIndex,int offset){
	int j;
	for(int i=startIndex+offset;i<len;i+=offset){
		int temp=arr[i];
		for(j=i-offset;j>=0&&arr[j]>temp;j-=offset){
			arr[j+offset]=arr[j];	
		}
		arr[j+offset]=temp;
	}
}

//Shell排序
void shellSort(int *arr,int len){
	int offset=3;
	for(;offset>0;offset--){//offset步进值
		for(int startIndex=0;startIndex<offset;startIndex++){
			sort(arr,len,startIndex,offset);	
		}
	}
}

static int oneQuickSort(int *arr,int low,int high){
	int temp=arr[low];
	while(low < high){
		while(arr[high]>=temp && low<high){
			high--;
		}
		arr[low]=arr[high];
		while(arr[low]<=temp && low<high){
			low++;
		}
		arr[high]=arr[low];
	}
	arr[low]=temp;
	return low;
}

static void quickSortR(int *arr,int low, int high){
	if(low >= high){
		return;
	}
	int mid=oneQuickSort(arr, low, high);
	//printf("mid=[%d],low=[%d],high=[%d]\n", mid,low,high);
	//getchar();
	quickSortR(arr, low, mid-1);
	quickSortR(arr, mid+1, high);
}

//快速排序
void quickSort(int *arr,int len){
	quickSortR(arr,0,len-1);
}

